#!/usr/bin/env python
# -*- coding: utf-8 -*-

import random

import os
import sys
sys.path.append(os.path.join(os.path.dirname(__file__), '..'))
import utils.rand_kit as rand_kit
import quick_sort.quick_sort as qs

# 二分查找法，复杂度O(log(2)n)
def binary_search(arr, item):
    low = 0
    high = len(arr) - 1

    while low < high:
        mid = (low + high) / 2
        guess = arr[mid]
        # print("low: %d, high: %d, mid: %d, guess: %d" % (low, high, mid, guess))
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1

    if arr[low] == item: 
        return low
    else: 
        return None

if __name__ == "__main__":
    arr = rand_kit.rand_arr()
    qs.quick_sort(arr)
    item = arr[random.randint(0, len(arr) - 1)]

    print("find %d in [%s]: " % (item, ', '.join(str(i) for i in arr)))
    print(binary_search(arr, item))
